456D - A Lot of Games - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pi pair<int,ll>
#define fi first
#define se second
#define pb push_back
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
const int N=2e5+5;
const int mod=1e9+7;

int trie[100005][26];
int now=1;
void add(string s){
    int i=0,nxt=0;
    while(i<s.size()){
        int c=s[i]-'a';
        if(trie[nxt][c]!=-1){
            nxt=trie[nxt][c];
        }else{
            nxt=trie[nxt][c]=now++;
            //cout<<nxt<<' '<<c<<' '<<trie[nxt][c]<<endl;
        }
        i++;
    }
}
bool dp1[100005],dp2[100005];

bool rec1(int x){
    bool ret=0;
    for(int i=0;i<26;i++){
        if(trie[x][i]!=-1){
            ret|=(!rec1(trie[x][i]));
        }
    }
    return dp1[x]=ret;
}
bool ch(int x){
    for(int i=0;i<26;i++){
        if(trie[x][i]!=-1)return false;
    }
    return true;
}
bool rec2(int x){
    bool ret=0;
    if(ch(x))return dp2[x]=1;
    for(int i=0;i<26;i++){
        if(trie[x][i]!=-1){
            ret|=(!rec2(trie[x][i]));
        }
    }
    return dp2[x]=ret;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n,k;cin>>n>>k;
    memset(trie,-1,sizeof trie);
    for(int i=0;i<n;i++){
        string s;cin>>s;
        add(s);
    }
    rec1(0);
    rec2(0);

    if(dp1[0]&&dp2[0]){
        cout<<"First"<<endl;
    }else if(!dp1[0]){
        cout<<"Second"<<endl;
    }else{
        if(k&1){
            cout<<"First"<<endl;
        }else{
            cout<<"Second"<<endl;
        }
    }
}